const int mod=1e9+7;
public:
    int add(int a,int b)
    {
        return (a%mod+b)%mod;
    }
    int waysToStep(int n) 
    {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        // vector<int>dp(n+1);
        // dp[0]=0;
        // dp[1]=1;
        // dp[2]=2;
        // dp[3]=4;
        int a=1,b=2,c=4,tem=0;
        for(int i=4;i<=n;i++)
        {
            tem=add(add(b,a),c)%mod;
            a=b;
            b=c;
            c=tem;
        }
        return tem;
    }